package com.lw.leetcode.add.e;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 这道题我不懂，记录一下。。
 * 956. 最高的广告牌
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/12 17:12
 */
public class TallestBillboard {

    public static void main(String[] args) {
        TallestBillboard test = new TallestBillboard();

        // 6
//        int[] arr = {1, 2, 3, 6};

        // 10
//        int[] arr = {1, 2, 3, 4, 5, 6};

        // 2129
//        int[] arr = {195, 82, 70, 102, 421, 444, 249, 268, 170, 105, 68, 72, 372, 322, 328, 340, 325, 72, 205, 153};

        //
//        int[] arr = Utils.getArr(20, 1, 500);
        // 900
//        int[] arr = {102, 101, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100};

        // 900
        int[] arr = {1, 2};

        int i = test.tallestBillboard(arr);
        System.out.println(i);
    }

    public int tallestBillboard(int[] rods) {
        int l = rods.length;
        int size = 0;
        for (int rod : rods) {
            size += rod;
        }
        int[][] arr = new int[l + 1][size + 1];

        for (int[] ints : arr) {
            Arrays.fill(ints, Integer.MIN_VALUE);
        }
        arr[0][0] = 0;
        for (int i = 1; i <= l; i++) {
            int v = rods[i - 1];
            for (int j = 0; j <= size; j++) {
                arr[i][j] = Math.max(arr[i][j], arr[i - 1][j]);
                if (j + v <= size) {
                    arr[i][j + v] = Math.max(arr[i][j + v], arr[i - 1][j]);
                }
                if (j > v) {
                    arr[i][j - v] = Math.max(arr[i][j - v], arr[i - 1][j] + v);
                } else {
                    arr[i][v - j] = Math.max(arr[i][v - j], arr[i - 1][j] + j);
                }
            }
        }
        return arr[l][0];
    }

    /*
     * 状态定义
     * f[i][j]:从前i个钢筋中挑出一部分并分成两堆，这两堆钢筋的长度和的差值为j的情况下较小的那一堆的和的最大值
     * 状态转移
     * 考虑当前遍历的钢筋i，假设长度为len。我们枚举之前的差值j，那么我们有几种情况
     * 1、不使用当前钢筋
     * f[i][j] = f[i-1][j]。
     * 根据我们的状态定义，这是很容易理解的，没问题。翻译一下就是:从前i个钢筋中挑出一部分并分成两堆，这两堆钢筋的长度和的差值为j的情况下较小的那一堆的和的最大值 等于 从前i-1个钢筋中挑出一部分并分成两堆，这两堆钢筋的长度和的差值为j的情况下较小的那一堆的和的最大值。这在不使用钢筋i的情况下显然是相等的。
     * 2、将当前钢筋放在较大的堆里，较小的那一堆不会发生任何改变！
     * f[i][j+len] = f[i-1][j]
     * 3、将当前钢筋放在较小的堆里，较小的那一堆的和增大len，但是仍然不超过较大的那一堆的和！
     * f[i][j-len] = f[i-1][j]+len
     * 4、将当前钢筋放在较小的堆里，较小的那一堆的和增大len，并且超过了较大的那一堆的和！此时较小堆的身份发生了改变，原来的较大堆变成了现在的较小堆。因为原来的较小堆和较大堆的差值为j，所以原来的较大堆是f[i-1][j]+j。
     * f[i][len-j] = f[i-1][j]+j
     *
     * 作者：lmf_1407
     * 链接：https://leetcode.cn/problems/tallest-billboard/solution/by-lmf_1407-y0kp/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */

}
